package doublePointer;

/*
* 42. 接雨水
*    双数组记录左右最大值
* 或者简化为双指针记录: 当height[left]<heiht[right]是时必有leftMax<rightMax;
* */
public class Trap42 {
    public int trap(int[] height){
        int left=0,right=height.length-1,leftMax=0,rightMax=0;
        int res=0;
        while(left<right){
            leftMax=Math.max(leftMax,height[left]);
            rightMax=Math.max(rightMax,height[right]);
            if(height[left]<height[right]){
                res+=leftMax-height[left];
                ++left;
            }else{
                res+=rightMax-height[right];
                --right;
            }
        }
        return res;
    }
}
